/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-06 21:57:06
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-07 20:41:27
 * @FilePath: \LeetCode\51.n-皇后.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 *
 * 方法1：排列树
 * - 棋盘抽象化为 {0, 1, 2, 3, 4, 5, 6, 7, 8}
 * - 初始化棋盘保证棋子不在同一行/列，只用再考虑对角线
 */

#include <vector>
#include <string>
#include <iostream>

// @lc code=start
class Solution
{
public:
    std::vector<std::vector<std::string>> result;
    std::vector<std::string> rowsQ;                  // 字符串保存棋盘
    int chessBoard[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8}; // 每行皇后的位置 0 ~ n-1
    int m_n;

    inline bool judge(int i) // i: 当前放置皇后棋子的位置
    {
        for (int j = 0; j < i; j++)
        {
            /* 不在同一斜线上 */
            if (std::abs(i - j) == std::abs(chessBoard[i] - chessBoard[j]))
                return false;
        }
        return true;
    }

    void sortTreeDFS(int i)
    {
        if (i == m_n)
        {
            for (int j = 0; j < m_n; j++)
            {
                rowsQ[j] = std::string(m_n, '.');
                rowsQ[j][chessBoard[j]] = 'Q';
            }
            result.emplace_back(rowsQ);
            return;
        }

        for (int k = i; k < m_n; k++)
        {
            std::swap(chessBoard[i], chessBoard[k]);
            if (judge(i)) // 交换有效
            {
                sortTreeDFS(i + 1);
            }
            std::swap(chessBoard[i], chessBoard[k]);
        }
    }

    std::vector<std::vector<std::string>> solveNQueens(int n)
    {
        m_n = n;
        rowsQ.resize(n);

        sortTreeDFS(0);
        return result;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    solution.solveNQueens(8);

    for (auto v : solution.result)
    {
        for (auto s : v)
            std::cout << s << std::endl;
        std::cout << std::endl;
    }

    return 0;
}